/*public class test {
}*/
public class MergeSort {
    // 合并两个有序子数组：arr[left..mid] 和 arr[mid+1..right]
    private static void merge(int[] arr, int left, int mid, int right) {
        // 临时数组存储合并结果
        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;

        // 按顺序合并两个子数组
        while (i <= mid && j <= right) {
            temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
        }

        // 处理剩余元素（左子数组未遍历完）
        while (i <= mid) temp[k++] = arr[i++];
        // 处理剩余元素（右子数组未遍历完）
        while (j <= right) temp[k++] = arr[j++];

        // 临时数组结果拷贝回原数组
        System.arraycopy(temp, 0, arr, left, temp.length);
    }

    // 递归分治：拆分+合并
    private static void sort(int[] arr, int left, int right) {
        if (left >= right) return; // 基线条件：子数组长度≤1

        int mid = left + (right - left) / 2;
        sort(arr, left, mid); // 左半区排序
        sort(arr, mid + 1, right); // 右半区排序
        merge(arr, left, mid, right); // 合并有序子数组
    }

    // 测试
    public static void main(String[] args) {
        int[] arr = {8, 4, 5, 7, 1, 3, 6, 2};
        sort(arr, 0, arr.length - 1);
        System.out.print("归并排序结果：");
        for (int num : arr) System.out.print(num + " "); // 输出：1 2 3 4 5 6 7 8
    }
}